package class_0923dynamicprogram;

public class RobotWalk {
    public static int way(int start, int aim, int k, int N){
        return process(start, k, aim, N);
    }
    public static int process(int cur, int rest, int aim, int N){
        if(rest==0){
            return cur == aim ? 1:0;
        }
        if(cur == 1){
            return process(2, rest - 1, aim, N);
        }
        else if(cur == N){
            return process(N-1, rest - 1, aim, N);
        }
        else{
            return process(cur-1, rest - 1, aim, N) + process(cur+1, rest - 1, aim, N);
        }
    }
    public static void main(String[] args) {
        System.out.println(way(2, 4, 3, 7)); // 输出: 0
        System.out.println(way(3, 3, 2, 5)); // 输出: 2

    }
}

class RobotWalk2{
    public static int way(int start, int aim, int k, int N){
        int[][] dp = new int[N+1][k+1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = -1; //初始化dp数组。
            }
        }
        return process(start, k, aim, N, dp); //主方法
    }
    // 递归的返回值由什么决定？
    // cur:1--->N
    // rest:0--->k
    // 开 (N+1)*(k+1)。
    public static int process(int cur, int rest, int aim, int N,int[][] dp){
        if(dp[cur][rest] != -1){
            return dp[cur][rest]; //若之前求解过这个问题， 直接解决。
        }
        int ans = 0;
        if(rest==0){
            ans = cur == aim ? 1:0;
        }
        if(cur == 1){
            ans = process(2, rest - 1, aim, N, dp);
        }
        else if(cur == N){
            ans = process(N-1, rest - 1, aim, N, dp);
        }
        else{
            // 当前选择
            ans = process(cur-1, rest - 1, aim, N, dp) + process(cur+1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }
}
